#include <stdio.h>
#include <string.h>

int fibonacci_arr[4000005] = {0};

int fibonacci(int i) {
    if (i < 4) {
        fibonacci_arr[i] = i;
        return i;
    }
    return fibonacci_arr[i] =
                   (fibonacci_arr[i - 1] == 0 ? (fibonacci_arr[i - 1] = fibonacci(i - 1)) : fibonacci_arr[i - 1]) +
                   (fibonacci_arr[i - 2] == 0 ? (fibonacci_arr[i - 2] = fibonacci(i - 2)) : fibonacci_arr[i - 2]);
}

int max(int a, int b) {
    return a > b ? a : b;
}

void print_fibonacci(int n) {
    for (int i = 1; i <= n; ++i) {
        printf("%d ", fibonacci_arr[i]);
    }
    printf("\n");
}

/**
 * 给定的大数，求最大连续digt个数的乘积
 * @param num 大数
 * @param digt 连续的位数
 */
void pe8(char *num, int digt) {
    long long zero_count = 0, current = 1, res = 0;
    for (int i = 0; i < strlen(num); ++i) {
        if (i < digt) {
            current *= num[i] - '0';
        } else {
            if (num[i] == '0') {
                zero_count++;
            } else {
                current *= num[i] - '0';
            }
            if (num[i - digt] == '0') {
                zero_count--;
            } else {
                current /= num[i - digt] - '0';
            }
        }
        if (zero_count == 0 && current > res) {
            res = current;
        }
    }
    printf("%lld", res);
}

/**
 * 四个方向，连续四个数，哪个乘积最大
 */
void pe11() {
    int iy[] = {-1, 0, 1, 1};
    int jx[] = {1, 1, 1, 0};
    int arr[26][23] = {0};
    for (int i = 3; i < 23; ++i) {
        for (int j = 0; j < 20; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }
    int res = 0;
    for (int i = 3; i < 23; ++i) {
        for (int j = 0; j < 20; ++j) {
            for (int k = 0; k < 4; ++k) {
                int temp = 1;
                for (int l = 0; l < 4; ++l) {
                    temp *= arr[i + iy[k] * l][j + jx[k] * l];
                }
                if (temp > res) {
                    res = temp;
                }
            }
        }
    }
    printf("%d", res);
}

/**
 * 大数加法
 */
void big_num_plus() {
    char s1[100], s2[100] = {0};
    int i1[100] = {0}, i2[100] = {0}, i3[105] = {0};
    scanf("%s%s", s1, s2);

    int s1Len = strlen(s1), s2Len = strlen(s2);
    int maxLen = s1Len > s2Len ? s1Len : s2Len;
    for (int i = s1Len - 1; i >= 0; --i) {
        i1[s1Len - i - 1] = s1[i] - '0';
    }
    for (int i = s2Len - 1; i >= 0; --i) {
        i2[s2Len - i - 1] = s2[i] - '0';
    }
    for (int i = 0; i < maxLen; ++i) {
        i3[i] += i1[i] + i2[i];
        if (i3[i] > 9) {
            i3[i + 1]++;
            i3[i] -= 10;
            if (i == maxLen - 1) {
                maxLen++;
            }
        }
    }
    for (int i = maxLen - 1; i >= 0; --i) {
        printf("%d", i3[i]);
    }
}

/**
 * 大数乘法
 */
void big_num_multi() {
    char s1[100], s2[100] = {0};
    int i1[100] = {0}, i2[100] = {0}, i3[205] = {0};
    scanf("%s%s", s1, s2);

    int s1Len = strlen(s1), s2Len = strlen(s2);
    int maxLen = s1Len + s2Len - 1;
    for (int i = s1Len - 1; i >= 0; --i) {
        i1[s1Len - i - 1] = s1[i] - '0';
    }
    for (int i = s2Len - 1; i >= 0; --i) {
        i2[s2Len - i - 1] = s2[i] - '0';
    }
    for (int i = 0; i < s1Len; ++i) {
        for (int j = 0; j < s2Len; ++j) {
            i3[i + j] += i1[i] * i2[j];
        }
    }
    for (int i = 0; i < maxLen; ++i) {
        if (i3[i] > 9) {
            i3[i + 1] += i3[i] / 10;
            i3[i] = i3[i] % 10;
            if (i == maxLen - 1) {
                maxLen++;
            }
        }
    }
    for (int i = maxLen - 1; i >= 0; --i) {
        printf("%d", i3[i]);
    }
}

//todo 还没写完，有bug
void big_num_sub() {
    char s1[100], s2[100] = {0};
    int i1[100] = {0}, i2[100] = {0}, i3[105] = {0}, lend[105] = {0};
    scanf("%s%s", s1, s2);

    int s1Len = strlen(s1), s2Len = strlen(s2);
    int maxLen = max(s1Len, s2Len), nega = 0;
    for (int i = s1Len - 1; i >= 0; --i) {
        i1[s1Len - i - 1] = s1[i] - '0';
    }
    for (int i = s2Len - 1; i >= 0; --i) {
        i2[s2Len - i - 1] = s2[i] - '0';
    }
    for (int i = 0; i < maxLen; ++i) {
        i3[i] += i1[i] - i2[i];
        if (i3[i] < 0) {
            lend[i] = 1;
            i3[i + 1]--;
            i3[i] = 10 + i3[i];
            if (i == maxLen - 1) {
                maxLen++;
                nega = 1;
                break;
            }
        }
    }
    if (nega) {
        for (int i = 0; i < maxLen - 1; ++i) {
            if (i3[i] < 0) {
                break;
            } else if (i3[i] > 0) {
                i3[i] = (lend[i] == 0 ? 10 : 9) - i3[i];
            }
        }
        printf("-");
    }
    for (int i = maxLen - 1 - nega; i >= 0; --i) {
        printf("%d", i3[i]);
    }
}

void pe15() {
    long long arr[20][20] = {0};
    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < 20; ++j) {
            if (i == 0 || j == 0) {
                arr[i][j] = 1;
            } else {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
        }
    }
}

void pe18() {
    int arr[16][16] = {0};
    for (int i = 1; i < 16; ++i) {
        for (int j = 1; j <= i; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }
    int ans;
    for (int i = 1; i < 16; ++i) {
        for (int j = 1; j <= i; ++j) {
            arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - 1]) + arr[i][j];
            ans = max(ans, arr[i][j]);
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    printf("%d ", ans);
}

//int main() {
//    big_num_sub();
//    return 0;
//}